要使数组 \(c_{j}\) 不是 \(b_{i}\) 的约数，只要让数组 \(b\) 中只存最小的数，或者让数组 \(c\) 中只存最大的数，就可以满足要求。特别的，如果所有数都相等，那么不存在解。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 public static void solve () { int n = io.nextInt(); int [] arr = new int [n]; for (int i = 0 ; i < n; i++) { arr[i] = io.nextInt(); } Arrays.sort(arr); if (arr[0 ] == arr[n - 1 ]) { io.println(-1 ); return ; } int it = 0 ; while (arr[it] == arr[0 ]) it++; io.println(it + " " + (n - it)); for (int i = 0 ; i < it; i++) io.print(arr[i] + " " ); io.println(); for (int i = it; i < n; i++) io.print(arr[i] + " " ); io.println(); }
要最大化 \(\sum_{i=1}^{n}\min_{j=1}^{m_{i}}a_{i,j}\)，一开始想到最大化最小值，二分？但是有点不太对。然后发现规律，只需要关注数组的最小值和次小值就行。首先所有数组的最小值的最小值一定会被包含在内，这样只要把其他数组的最小值移动到该最最小值所属的数组就可以让答案最大。也就是说答案等于所有数组次小值的和加上最最小值，再减去最最小值对应的次小值。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 public static void solve () { int n = io.nextInt(); int min1 = Integer.MAX_VALUE, min2 = Integer.MAX_VALUE; long sum = 0 ; List<Integer>[] arr = new List [n]; Arrays.setAll(arr, k -> new ArrayList <>()); for (int i = 0 ; i < n; i++) { int m = io.nextInt(); for (int j = 0 ; j < m; j++) { arr[i].add(io.nextInt()); } Collections.sort(arr[i]); sum += arr[i].get(1 ); min1 = Math.min(min1, arr[i].get(0 )); min2 = Math.min(min2, arr[i].get(1 )); } io.println(sum - min2 + min1); }
题目要求 \((\sum_{i=1}^{n}p_{i}\cdot i)-(\max_{j=1}^{n}p_{j}\cdot j)\) 的最大值，前半部分的最大值的情况就是从小到大排列，但是后半部分不好处理，所以考虑枚举后半部分。从大到小枚举 \(\max_{j=1}^{n}p_{j}\cdot j\) 的值，然后在不超过该值的情况下尽可能使 \(\sum_{i=1}^{n}p_{i}\cdot i\) 的值变大。要让求和的部分变大，也就是让大的 \(p\) 尽可能靠后，可以使用 \(\frac{\max_{j=1}^{n}p_{j}\cdot j}{p}\) 求得 \(p\) 可以放置的最大 \(i\) 是多少，然后如果该位置已经占用，那么就向左寻找第一个未占用的位置。我们可以使用并查集维护位置的占用情况，如果当前位置占用就将它和左边的位置合并，这样 find(Math.min(n, i)) 就是左边第一个的未占用的位置。如果可以放置的位置不存在，那么说明枚举值太小，终止枚举。（也可以使用栈来维护位置的占用情况）
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 private static int [] f;private static int find (int x) { if (x != f[x]) f[x] = find(f[x]); return f[x]; } public static void solve () { int n = io.nextInt(), ans = 0 ; for (int mx = n * n; mx >= 1 ; mx--) { int sum = 0 ; boolean ok = true ; f = new int [n + 1 ]; for (int i = 0 ; i <= n; i++) { f[i] = i; } for (int i = n; i >= 1 ; i--) { int x = find(Math.min(n, mx / i)); if (x == 0 ) { ok = false ; break ; } sum += i * x; f[x] = f[x - 1 ]; } if (!ok) break ; ans = Math.max(ans, sum - mx); } io.println(ans); }
还有一个解法，但是不知道如何证明正确性，也是可以过的。其实比赛的时候我就猜了这个结论，但是当时没试。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 public static void solve () { int n = io.nextInt(), ans = 0 ; for (int i = 1 ; i <= n; i++) { int sum = 0 , max = 0 ; for (int j = 1 ; j <= n; j++) { int x = j < i ? j : n - j + i; sum += x * j; max = Math.max(max, x * j); } ans = Math.max(ans, sum - max); } io.println(ans); }
首先，显然向左传送不会比向右传送到达更远的地方。考虑只有一个区间的情况：如果起点在 \([l,b]\) 之间，那么可以最远到达 \(b\) 点；如果起点在 \((b,r]\) 之间（即不在 \([l,b]\) 之间），那么当前点就是最远的点。可以发现，能够到达的最远位置只与 \(l\) 和 \(b\)，以及起点位置有关。所以考虑将所有区间 \([l,b]\) 合并，对每个查询都查找当前起点所在的区间。如果在某个区间内，最远位置即为该区间的右端点；如果不在任何区间内，那么最远位置即为当前位置。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 public static void solve () { int n = io.nextInt(); int [][] portals = new int [n][2 ]; for (int i = 0 ; i < n; i++) { portals[i][0 ] = io.nextInt(); io.nextInt(); io.nextInt(); portals[i][1 ] = io.nextInt(); } Arrays.sort(portals, (a, b) -> a[0 ] - b[0 ]); List<int []> intervals = new ArrayList <>(); intervals.add(new int []{Integer.MIN_VALUE, Integer.MIN_VALUE}); for (int i = 0 ; i < n; i++) { int m = intervals.size(); if (intervals.get(m - 1 )[1 ] < portals[i][0 ]) { intervals.add(new int []{portals[i][0 ], portals[i][1 ]}); } else { intervals.get(m - 1 )[1 ] = Math.max(intervals.get(m - 1 )[1 ], portals[i][1 ]); } } int q = io.nextInt(); for (int i = 0 ; i < q; i++) { int x = io.nextInt(); int lo = 0 , hi = intervals.size() - 1 ; while (lo <= hi) { int mid = lo + (hi - lo) / 2 ; if (intervals.get(mid)[0 ] > x) hi = mid - 1 ; else lo = mid + 1 ; } io.print(Math.max(x, intervals.get(hi)[1 ]) + " " ); } io.println(); }